//Copyright (C) 2013 Julio Espindola
//
//This file is part of VSize Checkers.
//
//VSize Checkers is free software: you can redistribute it and/or modify
//it under the terms of the GNU General Public License as published by
//the Free Software Foundation, either version 3 of the License, or
//(at your option) any later version.
//
//VSize Checkers is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You should have received a copy of the GNU General Public License
//along with VSize Checkers.  If not, see <http://www.gnu.org/licenses/>.

package checkers;

import java.util.ArrayList;
import java.util.HashMap;

class Result
{
    int score;
    Move move;
   
    Result(int score, Move move)
    {
        this.score = score;
        this.move = move;
    }
}

class Ai
{
    static int limit = 0;
    static final int INF = 5000;
    static final int NEAR_INF = 4999;
    static Table table = new Table();
   
    static Move getBestMove(Board b, ArrayList<Move> moves, int depth)
    {
        Move move = null;
        
        for(int i = 2; i<=depth; i+=2)
        {
            Result res = negaScout(b, (ArrayList<Move>) moves.clone(), i, -INF, INF);
            if(limit > 0) break;
            move = res.move;
        }
       
        return move;
    }
   
    static Result negaScout(Board b, ArrayList<Move> moves, int depth, int alpha, int beta)
    {
        if((b.squares[0]&Board.GAME_OVER)!=0 || depth <= limit)
            return new Result(b.evaluate(), null);
       
        int originalIndex = 0;
        Entry entry = table.getEntry(b.hash);
        if(entry != null)
        {
            if(entry.depth >= depth && entry.exact)
            {
                return new Result(entry.score, moves.get(entry.moveIndex));
            }
            else
            {
                Move m = moves.get(0);
                moves.set(0, moves.get(entry.moveIndex));
                moves.set(entry.moveIndex, m);
                originalIndex = entry.moveIndex;
            }
        }
       
        int adaptiveBeta = beta;
        int bestScore = -INF;
        Move bestMove = null;
        int bestIndex = 0;
       
        for(int i=0; i<moves.size(); ++i)
        {
            Move move = moves.get(i);
            ArrayList<Move> newMoves = b.makeMove(move);
            Result res = negaScout(b, newMoves, depth-1, -adaptiveBeta, -alpha);
            int currentScore = -res.score;
           
            if(currentScore > bestScore)
            {
                if(adaptiveBeta == beta || depth <= 2)
                    bestScore = currentScore;
                else
                {
                    res = negaScout(b, newMoves, depth-1, -beta, -currentScore);
                    bestScore = -res.score;
                }
               
                bestMove = move;
                bestIndex = (i==0 || i==originalIndex) ? originalIndex-i : i;
            }
           
            b.undoMove(move);

            if(bestScore >= beta)
            {
                if(limit == 0)
                    table.storeEntry(new Entry(b.hash, bestScore, bestIndex, depth, false));
                return new Result(bestScore, bestMove);
            }
            
            if(bestScore > alpha) alpha = bestScore;
            adaptiveBeta = alpha+1;
        }
       
        if(limit == 0)
            table.storeEntry(new Entry(b.hash, bestScore, bestIndex, depth, true));
        return new Result(bestScore, bestMove);
    }
}
